/**
 * @file path_operations.cpp
 * @brief Demonstrates path-to-root operations
 */

#include "../complete_binary_tree.hpp"
#include <iostream>
#include <vector>
#include <functional>

int main() {
    std::cout << "=== Complete Binary Tree - Path Operations Example ===\n\n";

    // Create a tree with 8 leaves
    // Leaves store leaf indices, internal nodes store level information
    CompleteBinaryTree<int, std::string> tree(8);
    
    // Initialize leaves with their indices
    for (size_t i = 0; i < tree.leaf_count(); ++i) {
        tree[i] = static_cast<int>(i);
    }
    
    // Initialize internal nodes with level labels
    for (size_t i = 0; i < tree.internal_count(); ++i) {
        tree.internal_at(i) = "Internal_" + std::to_string(i);
    }

    // Example 1: Get path as vector (allocates memory)
    std::cout << "=== Method 1: Vector-based Path Retrieval ===\n";
    size_t leaf_idx = 7;
    auto path = tree.path_to_root(leaf_idx);
    
    std::cout << "Path from leaf " << leaf_idx << " to root:\n";
    std::cout << "  Starting at: Leaf_" << tree[leaf_idx] << "\n";
    for (size_t i = 0; i < path.size(); ++i) {
        std::cout << "  Level " << i + 1 << ": " << path[i].get() << "\n";
    }

    // Example 2: Output iterator version (minimal allocation)
    std::cout << "\n=== Method 2: Output Iterator ===\n";
    std::vector<std::reference_wrapper<std::string>> path_buffer;
    path_buffer.reserve(tree.depth());
    
    tree.path_to_root(5, std::back_inserter(path_buffer));
    
    std::cout << "Path from leaf 5 to root (using output iterator):\n";
    std::cout << "  Starting at: Leaf_" << tree[5] << "\n";
    for (auto& node : path_buffer) {
        std::cout << "  -> " << node.get() << "\n";
    }

    // Example 3: Zero-allocation functional traversal
    std::cout << "\n=== Method 3: Functional Traversal (Zero Allocation) ===\n";
    std::cout << "Modifying all nodes on path from leaf 3:\n";
    std::cout << "  Original root value: " << tree.internal_at(0) << "\n";
    
    tree.for_each_on_path(3, [](std::string& node) {
        node += "_modified";
    });
    
    std::cout << "  Modified root value: " << tree.internal_at(0) << "\n";

    // Example 4: Count nodes on path
    std::cout << "\n=== Method 4: Custom Path Analysis ===\n";
    int visit_count = 0;
    tree.for_each_on_path(6, [&visit_count](std::string& node) {
        visit_count++;
        std::cout << "  Visiting: " << node << "\n";
    });
    std::cout << "Total nodes visited: " << visit_count << "\n";

    // Example 5: Different leaves, different paths
    std::cout << "\n=== Method 5: Comparing Different Paths ===\n";
    for (size_t leaf = 0; leaf < 4; ++leaf) {
        auto p = tree.path_to_root(leaf);
        std::cout << "Leaf " << leaf << " -> root: " << p.size() << " hops\n";
    }

    // Example 6: Using const version
    std::cout << "\n=== Method 6: Const Path Retrieval ===\n";
    const auto& const_tree = tree;
    auto const_path = const_tree.path_to_root(2);
    std::cout << "Const path from leaf 2 has " << const_path.size() << " nodes\n";

    std::cout << "\n=== Example Complete ===\n";
    return 0;
}
